package main.java.indi.zyj.acm;

import main.java.indi.zyj.hot100.base.ListNode;

public class IsPalindrome {

    public boolean isPalindrome(ListNode head) {

        if (head == null) {
            return true;
        }

        ListNode half = lookHalf(head);
        ListNode reverse = reverse(half.next);

        ListNode p1 = head, p2 = reverse;
        while (p1 != null && p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }


    public ListNode lookHalf(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head) {
        ListNode top = new ListNode(-1);
        ListNode p = head, q;
        while (p != null) {
            q = p.next;
            p = p.next;
            q.next = top.next;
            top.next = q;
        }
        return top.next;
    }

}
